package com.kevin.Code.OfferReviewVersion2;

/**
 * @author Vinlee Xiao
 * @Classname RedundantConnection
 * @Description Leetcode 684. 冗余连接 同剑指Offer 剑指 Offer II 118. 多余的边 中等难度
 * @Date 2022/1/22 12:00
 * @Version 1.0
 */
public class RedundantConnection {
    /**
     * @param edges
     * @return
     */
    public int[] findRedundantConnection(int[][] edges) {

        int row = edges.length;

        int[] parent = new int[row];

        for (int i = 0; i < row; i++) {
            parent[i] = i;
        }

        for (int[] edge : edges) {
            if (!isUnion(parent, edge[0], edge[1])) {
                return edge;
            }
        }

        return new int[2];


    }

    /**
     * @param parent
     * @param fromVertex
     * @param toVertex
     * @return
     */
    private boolean isUnion(int[] parent, int fromVertex, int toVertex) {

        int commonParent1 = findCommonParent(parent, fromVertex - 1);
        int commonParent2 = findCommonParent(parent, toVertex - 1);

        if (commonParent1 != commonParent2) {
            parent[commonParent1] = commonParent2;
            return true;
        }

        return false;
    }

    /**
     * @param parent
     * @param parentVertex
     * @return
     */
    private int findCommonParent(int[] parent, int parentVertex) {
        if (parent[parentVertex] != parentVertex) {
            return findCommonParent(parent, parent[parentVertex]);
        }

        return parent[parentVertex];
    }
}
